/*
Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
*/

class Solution {
public:
    int singleNumber(int A[], int n) {
        map<int,int> value_count;
        map<int,int>::iterator iter;
        for(int i=0; i<n; i++)
            value_count[A[i]] = 0;
        for(int i=0; i<n; i++)
            value_count[A[i]] += 1;
            
        for(iter=value_count.begin(); iter!=value_count.end(); ++iter){
              if(iter->second == 1) return iter->first;
        }
    }
};